redis篇——LRU cache设计指南

发表于 | | 阅读次数: |

1. LRU cache是什么？

LRU cache是一个缓存系统，特殊之处在于缓存的容量是有限的，当缓存内容超出预设容量之后，会淘汰最久未访问的缓存内容。

在很多架构设计中，常常出现LRU cache的身影，它是用来平衡成本和缓存命中率矛盾问题，采取的折中思路之一。在有限的缓存容量下，尽可能多的命中缓存内容。

2. 基于redis实现LRU cache

redis是开源的、内存型的存储系统，其内置了多种常见的数据类型和丰富的淘汰策略，可以很方便的基于redis实现一个LRU cache系统。redis基本介绍见：https://zhuanlan.zhihu.com/p/132353640

2.1 redis设置cache最大容量

假设限制redis最大cache容量为100mb，那么在redis.conf以下配置：

1
maxmemory 100mb

当缓存内容持续上涨，突破到100mb之后，就会触发redis的数据驱除策略。

2.2 redis数据驱除策略

目前redis的数据驱除策略有以下几种：

  1. noeviction：不驱除，新增数据会失败，无法再新增缓存。
  2. allkeys-lru: LRU方式驱除，将最久未访问的key清掉、释放空间。
  3. volatile-lru: LRU方式驱除，不同之处在于：只从已经过期的key列表中驱除最久未访问的key。
  4. allkeys-random: 随机驱除。
  5. volatile-random: 从过期的key列表中，随机驱除。
  6. volatile-ttl: 不立马驱除key，只是给key一个更小的ttl（延迟删除）。

备注：对于volatile-lru, volatile-random, volatile-ttl如果没有找到符合条件的key，就不会驱除。

需要根据业务访问场景选择合适的驱除策略，值得一提的是，我们可以在redis运行期间动态修改驱除策略。

不同策略选择原则大致为：

  1. allkeys-lru: 请求符合幂律分布，最近访问的元素有大概率被再次访问的场景。
  2. allkeys-random: 所有元素访问频率是相同的场景。
  3. volatile-ttl: 缓存内容均拥有不同的ttl的场景。

2.3 小结

通过为redis设置最大容量和数据LRU驱除策略，就可以很方便的实现一个LRU系统。

3. redis LRU算法简介

redis的LRU算法并不是完全意义上的LRU，它只是一个近似实现，这再一次的体现了工程架构设计中的折中思想。

3.1 redis近似LRU算法

由于LRU算法需要保存每一个元素的访问时间，如果元素数量特别多、频繁驱除的情况下，是非常消耗计算和内存的。为了成本和效果之间的折中，redis实现一个近似的LRU算法。

redis为对key集合进随机抽样，只对抽样集合中的key做LRU算法。样本集合小的情况下，计算和内存会极大降低，但是也会损失一点精度。可以通过这个配置来控制精度：

1
2
# 每次驱除抽样的key数目，越大LRU越精准
maxmemory-samples 5

3.2 redis更高级的LFU算法

当maxmemory-samples=10之后就接近真实LRU的效果了，无法继续提升。为了进一步提升命中效果，redis的大佬们又想到了一种办法：LFU（最近不频繁访问的驱除算法，在redis 4.0版本）

LRU vs LFU：

  1. LRU: 只是针对访问时间，对于最近刚刚访问的冷门数据来说，是需要一段时间才能被驱除掉。
  2. LFU: 实时记录每个key的访问次数，当触发驱除时，只驱除访问频度最低的那些key。

LFU同样提供了两种数据过期策略：volatile-lfu 和 allkeys-lfu，分别是过期集合和全集中选择目标。

除此之外为了控制访问频率计数器的增长和衰弱速度，redis又引入了两个配置:

1
2
3
4
# 增长速度：越大越慢
lfu-log-factor 10
# 衰减速度: 分钟单位
lfu-decay-time 1

LFU思想还是非常值得借鉴的，后面有机会再深入了解一下LFU算法。

4. 总结

redis非常强大，在很多场景中均有不俗的表现，今天主要介绍了LRU cache场景。

redis的配置参数也非常的多，给予了用户非常大的灵活性，如果redis集群很大的情况下，值得折腾一下各个配置，整个玄学调参。